// 设计一个支持以下两种操作的数组解构
// void addNum(int num): 从数据流重添加一个整数到数据结构中
// double findMedian(), 返回目前所有元素的中位数

// 解题思路

// 使用一个大顶堆queMax记录小于中位数的树，使用一个小顶堆queMin记录大于中位数的数
// - 当添加元素数量为偶数，queMin和queMax中元素数量相同，则中位数为它们队头的平均值
// - 当添加元素数量为奇数，queMin比queMax多一个，此时中位数为queMin的队头

// 为了满足上述条件，在进行addNum时，应当分情况处理：
// 1. num > max(queMin),此时num大于中位数，将其添加到大顶堆queMax中，新的中位数将大于原来的中位数，所以可能需要将queMax中的最小数移动到queMin中
// 2. num <= max(queMin),此时num小于中位数，将该数添加到小顶堆queMin中，新的中位数将小于等于原来的中位数，所以可能需要将queMin中最大数移动到queMax中
const {HeapQueue} = require('../../2. 优先队列/1. 二叉堆实现优先队列')
const heapq = new HeapQueue()

function MedianFinder () {
    this.queMin = []  // 存放小于中位数的值
    this.queMax = []  // 存放大于中位数的值
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {
    if (!this.queMin.length || num < this.queMin[0]) {
        heapq.heappush(this.queMin, num)
        if (this.queMax.length + 1 < this.queMin.length) {
            heapq.heappush(this.queMax, heapq.heappop(this.queMin))
        }
    } else {
        heapq.heappush(this.queMax, -num)
        if (this.queMax.length > this.queMin.length) {
            heapq.heappush(this.queMin, -heapq.heappop(this.queMax))
        }
    }

    
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {
    if (this.queMin.length > this.queMax.length) {
        return this.queMin[0]
    }
    return (this.queMin[0] + this.queMax[0]) / 2
};

let obj = new MedianFinder()
obj.addNum(1)
obj.addNum(2)
obj.addNum(10)
obj.addNum(5)
obj.addNum(4)
console.log(obj.findMedian()) 